Matching theory
1 Systems of Distinct Representatives(SDR)
SDR: 对于集合$S_1,S_2,\cdots,S_m$, 选出不同的$x_1,x_2,\cdots,x_m$, $x_i\in S_i$, $i=1,2,\cdots,m$
1.1 Hall’s marriage theorem
Hall定理: 集合$S_1,S_2,\cdots,S_m$存在SDR当且仅当
证明:
$m=1$时, 显然.
$m>1$时, 定义critical family: $S_1,S_2,\cdots,S_k$, $k<m$, $|\bigcup_{i=1}^kS_i|=k$.
case 1. 没有critical family, 即对于任何$I\subset \{1,2,\cdots,m\}$, $|\bigcup_{i\in I}S_i|>|I|$. 任意选择$x\in S_m$作为$S_m$的代表, 去掉$S_m$和$x$后, $S_i’=S_i\setminus\{x\}$. 对于任意$I\subseteq \{1,2,\cdots,m-1\}$, $|\bigcup_{i\in I}S_i|\ge |\bigcup_{i\in I}S_i|-1\ge |I|$. 根据归纳假设, 得证.
case 2. 存在一个critical family, 即存在$I\subset \{1,2,\cdots,m\}$, $|I|<m$, $|\bigcup_{i\in I}S_i|=|I|$. 假设$S_{m-k+1}, \cdots,S_m$是恰好满足Hall条件(取等)的$k<m$元集. 根据假设, 有SDR: $x_{m-k+1}\in S_{m-k+1}, \cdots,x_{m}\in S_{m}$. 去掉这$k$个元素, $S_i’=S_i\setminus \{x_{m-k+1}, \cdots,x_m\}$, $1\le i\le m-k$. 根据Hall条件, 对于任意$I\subseteq \{1,2,\cdots,m-k\}$, 记$S=\bigcup_{i\in I}S_i \cup\bigcup_{i=m-k+1}S_i$, $|S|\ge |I|+k$, 所以$|\bigcup _{i\in I}S_i’|\ge |S|-|\bigcup_{i=m-k+1}^m S_i|\ge |I|$. 根据假设, 存在$S_1,\cdots,S_{m-k}$的SDR, 和前面的SDR合起来就得到了答案.
Hall定理(图论版本):
二部图$G(U,V,E)$有$U$的匹配当且仅当对于所有$S\subseteq U$都有$|N(S)|\ge |S|$